\documentclass[twoside,a4paper]{article}
\usepackage{geometry}
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}

% useful packages.
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{fancyhdr}
\usepackage{layout}
\usepackage{tikz}

% some common command
\newcommand{\dif}{\mathrm{d}}
\newcommand{\avg}[1]{\left\langle #1 \right\rangle}
\newcommand{\difFrac}[2]{\frac{\dif #1}{\dif #2}}
\newcommand{\pdfFrac}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\OFL}{\mathrm{OFL}}
\newcommand{\UFL}{\mathrm{UFL}}
\newcommand{\fl}{\mathrm{fl}}
\newcommand{\op}{\odot}
\newcommand{\Eabs}{E_{\mathrm{abs}}}
\newcommand{\Erel}{E_{\mathrm{rel}}}

\begin{document}

\pagestyle{fancy}
\fancyhead{}
\lhead{NAME Jiatu Yan}
\chead{Numerical ODE/PDE Homework\#2}
\rhead{Date 2021.5.1}


\section*{Exercise 7.53 Complete the proof of Theorem 7.49.}
Firstly, we prove that for any continuous function $f\left( t \right)=\left( f_1\left( t \right),\ldots,f_n\left( t \right)   \right) $,
$f_i:\mathbb{R}\rightarrow\mathbb{R}$, there exists an inequality based on 2-norm
\[
	\mid  \mid \int_a^b f\left( t \right)\dif t  \mid  \mid \le \int_a^b  \mid  \mid f\left( t \right) \mid  \mid \dif t 
.\]

For $n=1$, the inequality is obviously achieved by replacing 2-norm with absolute value.
\[
\mid \int_a^b f\left( t \right)\dif t  \mid \le \int_a^b   \mid f\left( t \right) \mid \dif t 
.\]

For $n=2$, the inequality is achieved by viewing  $\mathbb{R}^2$ as $\mathbb{C}$.

We assume that for $n\le k$, the inequality is achieved.
Then for  $n = k + 1$, we have
\begin{equation*}
	\begin{split}
		\mid  \mid \int_a^b f\left( t \right)\dif t  \mid  \mid
		&=\sqrt{ \sum_{i=1}^{k + 1}\lbrack \int_a^b f_i\left( t \right) \dif t \rbrack^2 }\\
		&=\sqrt{ \sum_{i=1}^{k}\lbrack \int_a^b f_i\left( t \right) \dif t \rbrack^2 
			+ \lbrack\int_a^b f_{k+1}\left( t \right)  \rbrack^2  }\\
		&\le \sqrt{\left(\int_a^b\sqrt{(f_1\left( t \right))^2+\ldots+(f_k\left( t \right))^2  }\dif t\right)^2
		+ \lbrack\int_a^b f_{k + 1}\left( t \right)\dif t\rbrack^2 }\\
		&\le \int_a^b\sqrt{\lbrack\sqrt{f_1\left( t \right)^2+\ldots+f_k\left( t \right)^2  } \rbrack^2
		+f_{k+1}\left( t \right)^2 }\dif t\\
		&=\int_a^b\sqrt{f_1\left( t \right)^2+\ldots+f_{k+1}\left( t \right) ^2 }\dif t\\
		&=\int_a^b  \mid  \mid f\left( t \right) \mid  \mid \dif t. \\
	\end{split}
\end{equation*}
The first inequality is achieved by the induction basis and the second one is achieved by the situation when $n=2$.

Theorem 7.48 has already proved the existence and uniqueness of the solution of the IVP.
To prove the IVP in Definition 7.4 is well-posed, we only need to prove that it is insentive to the perturbation on both initial value and the ODEs.
So we take a small positive constant $\epsilon$ and two IVPs that satisfy
\[
\left\{
	\begin{array}{l}
		v'=f(v,t)\\
		v\left( 0 \right) =v_0\\
	\end{array}
\right.
,\qquad
\left\{
	\begin{array}{l}
		w'=f\left( w,t \right)+\delta\left( t \right)  \\
		w\left( 0 \right)=w_0\\ 
	\end{array}
\right.
,\qquad
\left\{
	\begin{array}{l}
		\forall t\in\lbrack0, \mathrm{T}\rbrack\quad   \mid \mid \delta\left( t \right)   \mid \mid <\epsilon\\
		 \mid  \mid v_0 - w_0 \mid  \mid <\epsilon\\
	\end{array}
\right.
.\] 
$\forall t\in\lbrack 0, \mathrm{T}\rbrack$, we can solve the two IVP by 
\begin{equation*}
	\begin{split}
		v\left( t \right)&=v\left( 0 \right)+\int_{0}^{t}f\left( v\left( s \right), s  \right)\dif s,\\
		w\left( t \right)&=w\left( 0 \right)+\int_{0}^{t}\lbrack f\left( w\left( s \right), s  \right) 
		+ \delta\left( s \right)\rbrack \dif s.\\
	\end{split}
\end{equation*}
Thus we have
\begin{equation*}
	\begin{split}
		v\left( t \right) - w\left( t \right)&=v_0 - w_0 + 
		\int_{0}^{t}\lbrack f\left( v\left( s \right),s  \right) - f\left( w\left( s \right),s \right)
		- \delta\left( s \right)   \rbrack \dif s,\\
	\end{split}
\end{equation*}
Take the 2-norm on both sides of the equation, we have
\begin{equation}
	\label{inequality_1}
	\begin{split}
		\mid  \mid v\left( t \right)-w\left( t \right)  \mid  \mid 
		&= \mid  \mid v_0 - w_0+ 
		\int_{0}^{t}\lbrack f\left( v\left( s \right),s  \right) - f\left( w\left( s \right),s \right)
		- \delta\left( s \right)   \rbrack \dif s \mid  \mid \\
		&\le  \mid  \mid v_0-w_0 \mid  \mid + 
		\mid  \mid \int_0^t\lbrack f\left( v\left( s \right) ,s \right)
		-f\left( w\left( s \right),s  \right)-\delta\left( s \right)\rbrack\dif s \mid  \mid\\
		&\le  \mid  \mid v_0 - w_0 \mid  \mid 
		+\int_0^t \mid  \mid f\left( v\left( s \right),s  \right) 
		-f\left( w\left( s \right) ,s \right)-\delta\left( s \right) \mid  \mid \dif s\\
		&\le  \mid  \mid v_0 - w_0 \mid  \mid 
		+\int_0^t \mid  \mid f\left( v\left( s \right),s  \right)-f\left( w\left( s \right),s  \right) \mid  \mid\dif s
		+\int_0^t \mid  \mid \delta\left( s \right) \mid  \mid \dif s\\
		&\le \epsilon + \int_0^t L \mid  \mid v\left( s \right)-w\left( s \right) \mid  \mid \dif s
		+ \int_0^t \epsilon \dif s \\  
		&=\left( 1+t \right)\epsilon + \int_0^tL \mid  \mid v\left( s \right) - w\left( s \right) \mid  \mid \dif s.\\   
	\end{split}
\end{equation}
We define a function $h\left( s \right), s\in\lbrack 0,\mathrm{T}\rbrack $ as
\[
	h\left( s \right)=e^{-sL}\int_0^s L \mid  \mid v\left( r \right)-w\left( r \right) \mid  \mid \dif r   
.\] 
Then we have
\[
	h'\left( s \right)=-Le^{-Ls}\int_0^sL\mid  \mid v\left( r \right)-w\left( r \right) \mid  \mid \dif r
	+e^{-Ls} L \mid  \mid v\left( s \right)-w(s) \mid  \mid     
.\] 
Take intergration on both sides, we have
\begin{equation*}
	\begin{split}
		h\left( t \right) -h\left( 0 \right)=h\left( t \right)
		&=\int_0^t\left(  \mid  \mid v\left( s \right)-w\left( s \right) \mid  \mid 
		-\int_0^sL \mid  \mid v\left( r \right)-w\left( r \right) \mid  \mid \dif r\right)Le^{-Ls}\dif s\\
		&\le \int_0^t\left( \left( 1+s \right)\epsilon
		+\int_0^sL \mid  \mid v\left( r \right)-w\left( r \right) \mid  \mid \dif r
	        -\int_0^sL \mid  \mid v\left( r \right)-w\left( r \right) \mid  \mid \dif r  \right)Le^{-Ls}\dif s\\
		&=\int_0^t\left( 1+s \right)\epsilon L e^{-Ls}\dif s.\\
	\end{split}
\end{equation*} 
The inequality is achieved by using the inequality(\ref{inequality_1}).
By the definition of $h\left( t \right) $ we have
\[
	h\left( t \right)= e^{-Lt}\int_0^tL \mid \mid w\left( r \right)-w\left( r \right) \mid  \mid \dif r
	\le \int_0^t\left( 1+s \right)\epsilon L e^{-Ls}\dif s 
.\] 
Put the above inequality back to inequality(\ref{inequality_1}), we have
\[
	\mid  \mid v\left( t \right)-w\left( t \right) \mid  \mid \le \left( 1+t \right)\epsilon 
	+ \int_0^t\left( 1+s \right)\epsilon Le^{L\left( t-s \right)}\dif s
	\le \left(1+T+\lbrack 1+T \right)TLe^{LT} \rbrack\epsilon\le Cs    
.\] 
Thus we have proved that the IVP in Definition 7.4 is \emph{well-posed}.

\section*{Exercise 7.132 Prove Theorem 7.131}
We can write the equation(8.69) when $n=-s+1,\ldots,0$ into a matrix form, which is
\[
\left[
\begin{array}{c c c c}
	-\alpha_{s-1}&-\alpha_{s-2}\ldots&-\alpha_0
\end{array}
\right]
\left[
\begin{array}{c c c c}
	\theta_0&\theta_1&\ldots&\theta_{s-1}\\
	\theta_{-1}&\theta_{0}&\ldots&\theta_{s-2}\\
	\vdots&\vdots&\ddots&\vdots\\
	\theta_{-s+1}&\theta_{-s}&\ldots&\theta_0\\
\end{array}
\right]
=\left[
\begin{array}{c c c c}
	\theta_1&\theta_2&\ldots&\theta_{s}\\
\end{array}
\right]
.\] 
Let A be the $s\times s$ matrix in the equation above. By the initial values of $\{\theta_n\}$, we have
\[
A=
\left[
\begin{array}{c c c c}
	\theta_0&\theta_1&\ldots&\theta_{s-1}\\
	\theta_{-1}&\theta_{0}&\ldots&\theta_{s-1}\\
	\vdots&\vdots&\ddots&\vdots\\
	\theta_{-s+1}&\theta_{-s}&\ldots&\theta_0\\
\end{array}
\right]
=
\left[
\begin{array}{c c c c}
	1&\theta_1&\ldots&\theta_{s-1}\\
	0&1&\ldots&\theta_{s-2}\\
	\vdots&\vdots&\ddots&\vdots\\
	0&0&\ldots&1\\
\end{array}
\right]
.\] 
It is obvious that A is nonsingular as its diagonal elements are all 1.
Thus we can rewrite the vector $[-\alpha_{s-1},\ldots,-\alpha_{0}]$ by $[\theta_1,\ldots,\theta_s]A^{-1}$.
By the equation(8.71) about $\{y_n\}$, we have
\begin{equation*}
	\begin{split}
		y_n&=-\sum_{i=0}^{s-1}\alpha_iy_{n-s+i}+\psi_n\\
		   &=
		   \left[
			   \begin{array}{c c c c}
				   -\alpha_{s-1}&-\alpha_{s-2}&\ldots&-\alpha_0\\
			   \end{array}
		   \right]
		   \left[
			   \begin{array}{c c c c}
				   y_{n-s+s-1}&
				   y_{n-s+s-2}&
				   \ldots&
				   y_{n-s}
			   \end{array}
		   \right]^{T}
		   +\psi_n\\
		   &=\left[
			   \begin{array}{c c c c}
				   \theta_1&\theta_2&\ldots&\theta_s\\
			   \end{array}
			   \right]
			   A^{-1}
			   \left[
				   \begin{array}{c c c c}
					   y_{n-1}&
					   y_{n-2}&
					   \ldots&
					y_{n-s}
				   \end{array}
			   \right]^{T}
			   +\psi_n.
	\end{split}
\end{equation*}

Now we prove the equation(8.72).

For $n=s$, we have
\begin{equation*}
	\begin{split}
		y_s&=-\sum_{i=0}^{s-1}\alpha_iy_i + \psi_s\\
		   &=\left[
			   \begin{array}{c c c}
				   \theta_1&\ldots&\theta_s
			   \end{array}
		   \right]
		   A^{-1}
		   \left[
			   \begin{array}{c c c}
				   y_{s-1}&
				   \ldots&
				   y_{0}
			   \end{array}
			   \right]^{T}
			   +\psi_s\theta_0\\
		   &=\left[
			   \begin{array}{c c c}
				   \theta_1&\ldots&\theta_s\\
			   \end{array}
		   \right]
		   \left[
			   \begin{array}{c c c}
				   \tilde{y}_{s-1}&
				   \ldots&
				   \tilde{y}_{0}
			   \end{array}
			   \right]^{T} + \theta_0\psi_s,
	\end{split}
\end{equation*}
which means equation(8.72) is satisfied.

Then we assume that equation(8.72) is right when $s\le n\le  k$.Then for $n=k+1$, we have
\begin{equation*}
	\begin{split}
		y_{k+1}=&\left[
			\begin{array}{c c c}
				-\alpha_{s-1}&\ldots&-\alpha_{0}
			\end{array}
		\right]
		\left[
			\begin{array}{c c c}
				y_{k}&\ldots&y_{k-s+1}
			\end{array}
		\right]^{T}
		+\theta_0\psi_{k+1}\\
			=&\left[
			       \begin{array}{c c c}
				       -\alpha_{s-1}&\ldots&-\alpha_0
			       \end{array}
		       \right]
		       (
		       \left[
			       \begin{array}{c c c}
				       \theta_{k-s+1}&\ldots&\theta_{k}\\
				       \theta_{k-s}&\ldots&\theta_{k-1}\\
				       \vdots&\ddots&\vdots\\
				       \theta_{k-s+1-s+1}&\ldots&\theta_{k-s+1}\\
			       \end{array}
		       \right]
		       A^{-1}
		       \left[
			       \begin{array}{c}
				       y_{s-1}\\
				       y_{s-2}\\
				       \vdots\\
				       y_{0}\\
			       \end{array}
		       \right]\\
		       &+
		       \left[
		       \begin{array}{c c c}
                                       -\alpha_{s-1}&\ldots&-\alpha_0
                               \end{array}
		       \right]
		       \left[
			\begin{array}{c}
				\sum_{i=s}^{k}\theta_{k-i}\psi_{i}\\
				\sum_{i=s}^{k-1}\theta_{k-1-i}\psi_{i} + \theta_{-1}\psi_{k}\\
				\vdots\\
				\sum_{i=s}^{k-s+1}\theta_{k-s+1-i}\psi_{i} + \sum_{i=k-s+2}^{k}\theta_{k-s+1-i}\psi_{i}\\
			\end{array}
		\right]
		)
		+\theta_0\psi_{k+1}\\
			=&\left[
		       \begin{array}{c c c c}
			       \theta_{k-s+1+1}&\theta_{k-s+1}&\ldots&\theta_{k+1}\\
		       \end{array}
		       \right]
		       A^{-1}
		       \left[
		       \begin{array}{c}
			       y_{s-1}\\
			       y_{s-2}\\
			       \vdots\\
			       y_{0}\\
		      \end{array}
		      \right]
		      -
		      \sum_{j=0}^{s-1}\alpha_{j}\left(\sum_{i=s}^{k}\theta_{k-s+1+j-i}\psi_{i}\right)
		      +\theta_0\psi_{k+1}\\ 
				=&\left[
		      \begin{array}{c c c}
			       \theta_{k+1-\left( s-1 \right) }&\ldots&\theta_{k+1}\\
		      \end{array}
		      \right]
		      \left[
		      \begin{array}{c c c}
			       \tilde{y}_{s-1}&\ldots&\tilde{y}_{0}\\
		      \end{array}
		      \right]^{T}+\sum_{i=s}^{k}\psi_i\left(-\sum_{j=0}^{s-1}\alpha_{j}\theta_{k+1-s-i+j}\right)
		      +\theta_0\psi_{k+1}\\
					=&\sum_{i=0}^{s-1}\theta_{k + 1-i}\tilde{y}_{i}+\sum_{i=s}^{k+1}\theta_{k+1-i}\psi_{i}.\\
	\end{split}
\end{equation*}

The second equation is based on the induction bases and $\theta_{i}=0$ for  $i<0$,
and the third and forth one is based on the equation(8.69) about $\{\theta_n\}$.
In the forth equation, I changed the order of summation in the second part of the formula.
Thus we proved that the equation(8.72) is right for all  $n\ge s$. 

\section*{Exercise 7.137 Prove Lemma 7.136}

For the sake of convenience, we assume that $\alpha_s = 1$ in this LMM. Otherwise, we can divide each coefficients with $\alpha_s$ to get $\alpha_s = 1$.
By Lemma 7.135 we have known that the convergent LMM is preconsistent, which means
\[
	\sum_{i=0}^{s}\alpha_i=0
.\] 
We can easily get the exact solution $u = t$.
If the LMM is not consistent, i.e. $\exists C$  satisfying
\[
	\sum_{i=0}^{s}\left(i\alpha_i-\beta_i\right)=-C \neq 0
.\] 
Apply the convergent LMM to the IVP
\[
	u'\left( t \right)=1;\qquad u\left( 0 \right)=0 
.\] 
Then $\forall k>0$, we can easily get the initial points $U_i = ik$, $i=0,1,\ldots,s-1$.
We can induce a equation about the solution errors, which is
\begin{equation*}
	\begin{split}
		&\sum_{i=0}^{s}\left(U_{n+i}\alpha_i-k\beta_i\right)=0 \qquad \left( n\ge 0 \right) \\
		&\Rightarrow \sum_{i=0}^{s}\left[\alpha_i\left( U_{n+i}-\left( n+i \right)k  \right)+n\alpha_i+
		i\alpha_ik-k\beta_i\right]=0\\
		&\Rightarrow \sum_{i=0}^{s}\alpha_iE_{n+i} = kC. 
	\end{split}
\end{equation*}
The second "$\Rightarrow$" is achieved by the preconsistency and definition of solution error.

For the linear difference equation
\[
	\sum_{i=0}^{s}\alpha_i\theta_i = 0
,\]
we can easily get the solution $\theta_n = 1$ by the preconsistency of the LMM.

Now by Theorem 7.131, we have
 \[
	 E_n = \sum_{i=0}^{s-1}\theta_{n-i}\tilde{E}_i + \sum_{i=s}^{n}\theta_{n-i}Ck
,\]
where
\begin{equation*}
\left[
	\begin{array}{c}
		\tilde{E}_{s-1}\\
		\tilde{E}_{s-2}\\
		\vdots\\
		\tilde{E}_0\\
	\end{array}
\right]
=
\left[
	\begin{array}{c c c c}
		1&1&\ldots&1\\
		0&1&\ldots&1\\
		\vdots&\vdots&\ddots&\vdots\\
		0&0&\ldots&1\\
	\end{array}
\right]
^{-1}
\left[
	\begin{array}{c}
		E_{s-1} = 0\\
		E_{s-2} = 0\\
		\vdots\\
		E_{0} = 0\\
	\end{array}
\right].
\end{equation*}
So we get $E_n = \sum_{i=s}^{n}Ck$. Thus we can estimate the solution on $T$, which is
 \[
	 E_N = \sum_{i=s}^{N}\frac{CT}{N}\approx \frac{NCT}{N} = \mathrm{O}\left( 1 \right) 
,\]
which contradicts with the condition that the LMM is convergent.

\section*{Exercise 7.154 Write a program to reproduce the RAS plots in Example 7.151, 7.152, 7.153}
I wrote a matlab program to draw the RAS plots of ABM, AMM and BDF method and determined which part of the plots
is the RAS. The plots are listed in Figure \ref{fig RAS} below.
\begin{figure*}[ht]
        \centering
	\begin{minipage}[t]{0.45\linewidth}
		\centering
                \includegraphics[width=8cm, height=8cm]{RAS_ABM_123.eps}
        \end{minipage}
	\begin{minipage}[t]{0.45\linewidth}
		\centering
                \includegraphics[width=8cm, height=8cm]{RAS_ABM_4.eps}
        \end{minipage}

	\begin{minipage}[t]{0.45\linewidth}
		\centering
                \includegraphics[width=8cm, height=8cm]{RAS_AMM_345.eps}
	\end{minipage}
	\begin{minipage}[t]{0.45\linewidth}
		\centering
                \includegraphics[width=8cm, height=8cm]{RAS_BDF_1234.eps}
	\end{minipage}
	\caption{Plots of RAS for some LMM}
	\label{fig RAS}
\end{figure*}

\section*{Exercise 7.159 Does the length of the thick red line segment in the above represent the one-step error?}
The length of the thick red line segment does not represent the one-step error,
it only represents an approximation to the one-step error.

The function in the picutre in Definition(7.158) is the true solution $u\left(t  \right) $
adding a constan t which is $U^{n} - u\left( t_n \right) $. 
Denote the slope of the function at $t_n$ as  $\tilde{y}_1$, we have
 \[
	 \tilde{y}_1 = u'\left( t_n \right) = f\left( u\left( t_n \right)  , t_n\right)  
.\] 
We notice that $y_1\neq\tilde{y}_1$, as $y_1 = f\left( U^n, t_n \right) $.
By the definition 7.158 we know that
\[
	y_2 = f\left(  U^n + \frac{k}{2}y_1, t_n + \frac{k}{2}\right) 
.\] 

We assume that the modified Euler method is 
 \[
	 U^{n+1} =U^n +  k\phi\left( U^n,t_n \right) = U^n + kf\left(U^n +\frac{k}{2}f\left( U^n,t_n  \right),t_n +\frac{k}{2} \right)    
.\] 
Thus we can decude $U^{n+1}$ and calculate the length of the thick red line segment $L$,
\begin{equation*}
	\begin{split}
		L = U^{n+1} - u\left( t_{n+1} \right) + u\left(t_n  \right)-U^n&=
		U^n + ky_2 - u\left( t_{n+1} \right) +u\left( t_n \right)-U^n\\
									       &=kf\left( U^n+\frac{k}{2}y_1,t_n+\frac{k}{2} \right)-u\left( t_{n+1} \right)+u\left( t_n \right)  \\
									       &=k\phi\left( u\left( t_n \right),t_n  \right) -u\left( t_{n+1} \right)+u\left( t_n \right).   
 \end{split}
\end{equation*}

While the one-step error at $t_{n+1}$ is
\[
	\mathcal{L}u\left( t_{n} \right) = u\left( t_{n+1} \right)-u\left( t_n \right)-k\phi\left( U^n, t_n \right)   
.\]

Then we calculate the difference between $\mathcal{L}\left( t_{n+1} \right) $ and $-L$, we have
\[
	\mathcal{L}\left( t_{n} \right) + L =  k\left[ \phi\left( u\left( t_n \right),t_n  \right)
	-\phi\left( U^n,t_n \right)   \right]
.\]
So it is the one-step error plus the error caused by 

\section*{Write down the Butcher tableux of the modified Euler method, the improved Euler method, and Heun's third-order method.}
The Butcher tableux of these methods are
\begin{equation*}
		\begin{tabular}{p{7mm}| p{7mm} p{7mm}}
			\multicolumn{3}{p{21mm}}{The modified Euler method}\\
			\hline
			\rule{0pt}{3.5mm}0&0&0\\
			\rule{0pt}{3.5mm}$\frac{1}{2}$ &$\frac{1}{2}$&0 \\
			\hline
			\rule{0pt}{3.5mm}	      &0&1\\
		\end{tabular}
		\quad
		\begin{tabular}{p{7mm}|p{7mm} p{7mm}}
			\multicolumn{3}{p{21mm}}{The improved Euler method}\\
		\hline
		\rule{0pt}{3.5mm}0&0&0\\
		\rule{0pt}{3.5mm}1&1&0\\
		\hline
		 \rule{0pt}{3.5mm}&$\frac{1}{2}$ &$\frac{1}{2}$ \\
	\end{tabular}
	\quad
	\begin{tabular}{p{7mm}|p{7mm} p{7mm} p{7mm}}
		\multicolumn{4}{p{21mm}}{Heun's third-order method}\\
		\hline
		\rule{0pt}{3.5mm}0&0&0&0\\
		\rule{0pt}{3.5mm}$\frac{1}{3}$ &$\frac{1}{3}$ &0&0\\
		\rule{0pt}{3.5mm}$\frac{2}{3}$ &0&$\frac{2}{3}$ &0\\
		\hline
			      \rule{0pt}{3.5mm}&$\frac{1}{4}$ &0&$\frac{3}{4}$ \\	
	\end{tabular}.
\end{equation*}

\section*{Rewrite the TR-BDF2 method.}

Rewrite the TR-BDF2 method, we have
\begin{equation*}
	\begin{split}
		U^{*}&=U^{n} + \frac{k}{4}f\left( U^{n},t_n \right)+\frac{k}{4}f\left( U^{*},t_n+\frac{k}{2} \right)\\
		U^{n+1}&=U^{n} + \frac{k}{3}f\left( U^{n},t_n \right) + \frac{k}{3}f\left( U^{*},t_n+\frac{k}{2} \right)
		+\frac{k}{3}f\left( U^{n+1},t_n+k \right) 
	\end{split}
\end{equation*}
Denote $f\left( U^{n},t_n \right), f\left(U^{*},t_n+\frac{k}{2}  \right),f\left( U^{n+1},t_n+k \right)  $ as 
$y_1,y_2,y_3$ respectively, we can get the standard form of the TR-BDF2 method which is
\begin{equation*}
	\begin{split}
		\left\{
			\begin{array}{l}
				\rule{0pt}{3.5mm}y_1 = f\left( U^{n},t_n \right)\\
				\rule{0pt}{3.5mm} y_2 = f\left( U^{n} + \frac{k}{4}y_1 + \frac{k}{4}y_2,t_n+\frac{k}{2} \right)\\
				\rule{0pt}{3.5mm}y_3 = f\left( U_n + \frac{k}{3}y_1+\frac{k}{3}y_2+\frac{k}{3}y_3,t_n+k \right)\\ 
				\rule{0pt}{3.5mm}   U^{n+1}=U^{n}+\frac{k}{3}y_1+\frac{k}{3}y_2+\frac{k}{3}y_3\\
			\end{array}
		\right..
	\end{split}
\end{equation*}

Thus the Butcher tabeau is
\begin{equation*}
	\begin{tabular}{p{9mm}| p{9mm} p{9mm} p{9mm}}
                        \multicolumn{3}{p{36mm}}{The TR-BDF2 method}\\
                        \hline
			\rule{0pt}{3.5mm}0&0&0&0\\
			\rule{0pt}{3.5mm}$\frac{1}{2}$ &$\frac{1}{4}$&$\frac{1}{4}$ &0\\
			\rule{0pt}{3.5mm}$1$&$\frac{1}{3}$ &$\frac{1}{3}$ &$\frac{1}{3}$ \\
			\hline
							   &$\frac{1}{3}$&$\frac{1}{3}$&$\frac{1}{3}$\\
		\end{tabular}
\end{equation*}

We can draw a figure for the TR-BDF2 method. The picture is shown in Figure \ref{p1}.
\begin{figure}[h]
	\centering
	\caption{Figure for the TR-BDF2 method}
	\label{p1}
\begin{tikzpicture}
        \draw[->] (0,0)--(7,0) node[below] {$x$};
        \draw[->] (0,0)--(0,5) node[above] {$y$};
	\draw[domain=0:6] plot (\x, -0.25*\x*\x+2*\x);
	\draw[blue,dashed] (2,0)--(2,3);
	\draw[blue,dashed] (0,3)--(2,3);
	\draw[red, domain=1:3.5] plot(\x, \x+1);
	\node [below] at (2, 0) {$t_n$};
	\node [left] at (0,3) {$U^{n}$};
	\draw[blue,dashed] (2.75,3.75)--(2.75,0);
	\node[below] at (2.75,0) {$t_n+\frac{k}{4}$};
	\draw[green, domain=2.5:4.5] plot(\x, 0.5*\x+2.375 );
	\draw[blue,dashed] (3.5,4.125)--(3.5,0);
	\draw[blue,dashed] (3.5,4.125)--(0,4.125);
	\draw[->](3.5, -1)--(3.5, 0);
	\node[below] at (3.5, -1) {$t_n+\frac{k}{2}$};
	\draw[->](-1,4.6)--(0,4.125);
	\node[left] at (-1, 4.6) {$U^n + \frac{k}{4}y_1+\frac{k}{4}y_2$};
	\draw[green, domain=3:4] plot(\x, 0.5*\x+2.5);
	\draw[brown, dashed] (3,0)--(3,4);
	\draw[brown,dashed] (3,4)--(0,4);
	\draw[->] (-1,4)--(0,4);
	\draw[->] (2.5,0.5)--(3,0);
	\node[above] at(2.5,0.5) {$t_n+\frac{k}{3}$};
	\node[left] at (-1, 4){$U^n + \frac{k}{3}y_1$};
	\draw[brown, dashed] (4,4.5) -- (4,0);
	\draw[brown,dashed] (4,4.5)--(0,4.5);
	\node[below] at(4.1,0) {$t_n+\frac{2k}{3}$};
	\draw[->] (-1,5)--(0,4.5);
	\node[left] at(-1,5) {$U^n + \frac{k}{3}y_1+\frac{k}{3}ya_2$};
	\draw[yellow, domain=4:6]plot (\x, -1*\x+8.5);
	\draw[brown, dashed] (5,3.5)--(5,0);
	\draw[brown, dashed] (5,3.5)--(0,3.5);
	\node[below] at (5.2,0){$t_{n+1}$};
	\node[left] at (0,3.5) {$U^n+1=U^n+\frac{k}{3}y_1+\frac{k}{3}y_2+\frac{k}{3}y_3$};
	\node[below] at(6.5,4) {$u(t)-u(t_n)+U^n$};
\end{tikzpicture}
\end{figure}
In the Figure \ref{p1}, the slope of the red line equals to $y_1$, and that of the green one and of the yellow one equals to $y_2$ and $y_3$ respectively. 

\section*{Derive the $\mathrm{O}\left( k^{3} \right) $ term in Example 7.175 to verify that it does not vanish.}
\begin{equation*}
	\begin{split}
		\mathcal{L}\left( t_n \right)=&u\left( t_{n+1} \right)-u\left( t_n \right)
		-kf\left( u\left( t_n \right)+\frac{k}{2}f\left( u\left( t_n \right),t_n  \right),t_n+\frac{k}{2}   \right)\\
		=&ku'\left( t_n+\frac{k}{2} \right)+\frac{k^{3}}{24}u'''\left( t_n+\frac{k}{2} \right)+\mathrm{O}\left( k^{5} \right)\\
		 &-kf\left( u\left( t_n+\frac{k}{2} \right)-\frac{k}{2}u'\left( t_n \right)-
		 \frac{1}{2}\left( \frac{k}{2} \right)^2u''\left( t_n \right)+\mathrm{O}\left( k^{3} \right)
	 +\frac{k}{2}u'(t_n),t_n+\frac{k}{2}\right)\\
		=&ku'\left( t_n+\frac{k}{2} \right)+\frac{k^{3}}{24}u'''\left( t_n+\frac{k}{2} \right)+\mathrm{O}\left( k^{5} \right)\\
		 &-kf\left( u\left( t_n+\frac{k}{2} \right) +\left[
		 -\frac{k^2}{8}u''\left( t_n \right)+\mathrm{O}\left( k^{3} \right)     \right],t_n+\frac{k}{2}  \right)\\
		=&ku'\left( t_n+\frac{k}{2} \right)+\frac{k^{3}}{24}u'''\left( t_n+\frac{k}{2} \right)+\mathrm{O}\left( k^{5} \right)\\
		 &-k\left\{f\left( u( t_n+\frac{k}{2}),t_n+\frac{k}{2}\right)+ \left[-\frac{k^2}{8}u''\left( t_n \right)+\mathrm{O}\left( k^{3} \right)  \right]f'\left( u(t_n+\frac{k}{2},t_n+\frac{k}{2})  \right)
		 +\mathrm{O}\left( k^{4} \right)  \right\}\\
		=&\frac{k^{3}}{24}u'''\left( t_n+\frac{k}{2} \right)+\frac{k^{3}}{8}u''\left( t_n+\frac{k}{2} \right)+\mathrm{O}\left( k^{4} \right).\\   
	\end{split}
\end{equation*}
The second equality is achieved by taylor expansion of u on $t_{n}+k /2$ and the forth one is achieved by taylor expansion of f on  $u(t_n+k /2)$.
Thus we have derived the $\mathrm{O}\left( k^{3} \right) $ term and we get that it does not invanish.

\section*{Exercise 7.184 Prove Lemma 7.183}

For the sake of convenience and do not lose generality, we denote $u^{\left( i \right) }\left( t_n \right) $ as $u^{(i)}$.
By definition we can deduce the one-step error, which is
\[
	\mathcal{L}u\left( t_n \right)=u\left( t_{n+1} \right)-u\left( t_n \right)-\frac{k}{6}\tilde{y}_1-\frac{k}{3}\tilde{y}_2-\frac{k}{3}\tilde{y}_3-\frac{k}{6}\tilde{y}_4   
,\]
where the $\tilde{y}_i$'s are
\begin{equation*}
	\begin{split}
		\tilde{y}_1 =& u'\left( t_n \right)\\
		\tilde{y}_2 =& f\left( u\left( t_n \right)+\frac{k}{2}\tilde{y}_1,t_n +\frac{k}{2}  \right)\\
		=&f\left( u(t_n+\frac{k}{2})-\frac{k^2}{8}u''-\frac{k^{3}}{48}u'''-\mathrm{O}\left( k^{4} \right),t_n+\frac{k}{2}   \right)\\
		=&f\left( u(t_n+\frac{k}{2}),t_n+\frac{k}{2} \right)
		+\left[ -\frac{k^2}{8}u''-\frac{k^{3}}{48}u''' - \mathrm{O}\left( k^{4} \right) \right]f'\left( u(t_n+\frac{k}{2}), t_n+\frac{k}{2} \right)+\mathrm{O}\left( k^{4} \right)\\
		=&u'+ \frac{k}{2}u''+\frac{k^2}{8}u'''+\frac{k^{3}}{48}u^{\left( 4 \right) }
		 -\frac{k^2}{8}\left( u'' \right)^{2}-\frac{k^{3}}{12}u''u'''+\mathrm{O}\left( k^{4} \right)\\  
		\tilde{y}_3=&f\left( u(t_n)+\frac{k}{2}\tilde{y}_2, t_n+\frac{k}{2} \right)\\
		=&f\left( u(t_n+\frac{k}{2})+\frac{k^2}{8}u''+\frac{k^{3}}{24}u'''-\frac{k^{3}}{16}\left( u'' \right)^2+\mathrm{O}\left( k^{4} \right),t_n+\frac{k}{2}   \right)\\ 
		=&f\left( u(t_n+\frac{k}{2}),t_n+\frac{k}{2} \right) 
		+\left[\frac{k^2}{8}u''+\frac{k^{3}}{24}u'''-\frac{k^{3}}{16}\left( u'' \right)^2+\mathrm{O}\left( k^{4} \right)    \right]f'\left( u(t_n+\frac{k}{2}), t_n+\frac{k}{2} \right) + \mathrm{O}\left( k^{4} \right) \\
		=&u'+\frac{k}{2}u''+\frac{k^2}{8}u'''+\frac{k^{3}}{48}u^{\left( 4 \right) }
		+\frac{5k^{3}}{48}u''u'''+\frac{k^2}{8}\left( u'' \right)^2-\frac{k^{3}}{16}\left( u'' \right)^{3}+\mathrm{O}\left( k^{4} \right) \\
		\tilde{y}_4=&f\left( u(t_n)+k\tilde{y}_3, t_n+k \right)\\
	=&f\left( u(t_n+k)-\frac{k^{3}}{24}u'''+\frac{k^{3}}{8}\left( u'' \right)^2+\mathrm{O}\left( k^{4}\right),t_n+k \right)\\
		=&f\left( u(t_n+k),t_n+k \right)
		+\left[\frac{k^{3}}{8}\left( u''\right)^2-\frac{k^{3}}{24}u'''+\mathrm{O}\left( k^{4} \right)  \right]f'\left( u(t_n+k),t_n+k \right)
		+\mathrm{O}\left( k^{4} \right) \\
		=&u'+ku''+\frac{k^2}{2}u'''+\frac{k^{3}}{6}u^{\left( 4 \right) }+\frac{k^{3}}{8}\left( u'' \right)^{3}-\frac{k^{3}}{24}u'''u''+\mathrm{O}\left( k^{4} \right).
	\end{split}
\end{equation*}
The second equation of each $\tilde{y}_i$ is achieved by the taylor expansion of $u$ on $t_n+k/2$ or on $t_n+k$. 
The third equation of each $\tilde{y}_i$ is achieved by taylor expansion of $f$ on $u\left( t_n+k/2 \right) $ or on $u\left( t_n+k \right) $. 
While the forth one is based on $u'=f\left( u,t \right) $ and the taylor expansion of $u$ on $t_n+k /2$ or on $t_n$. 

Now we can estimate the one-step error, we have
\begin{equation*}
	\begin{split}
		\mathcal{L}\left( u\left( t_{n} \right)  \right)
		=&u\left( t_{n+1} \right) - u\left( t_n \right)-\frac{k}{6}\tilde{y}_1-\frac{k}{3}\tilde{y}_2
		-\frac{k}{3}\tilde{y}_3-\frac{k}{6}\tilde{y}_4\\
		=&\left[u+ku'+\frac{k^2}{2}u''+\frac{k^{3}}{6}u'''+\frac{k^{4}}{24}u^{\left( 4 \right)}+\mathrm{O}\left( k^{5} \right) \right]
		-u-\frac{k}{6}u'\\
		 &+\left[-\frac{k}{3}u'-\frac{k^2}{6}u''-\frac{k^{3}}{24}u'''-\frac{k^{4}}{144}u^{\left( 4 \right) }
		+\frac{k^{3}}{24}\left( u'' \right)^2+\frac{k^{4}}{36}u''u''' + \mathrm{O}\left( k^{5} \right)  \right]\\
		 &+\left[-\frac{k}{3}u'-\frac{k^2}{6}u''-\frac{k^{3}}{24}u'''-\frac{k^{4}}{144}u^{\left( 4 \right)}
		 -\frac{5k^{4}}{144}u''u'''-\frac{k^{3}}{24}\left( u'' \right)^2+\frac{k^{4}}{48}(u'')^{3}+\mathrm{O}\left( k^{5} \right)  \right]\\
		 &+\left[-\frac{k}{6}u'-\frac{k^2}{6}u''-\frac{k^{3}}{12}u'''-\frac{k^{4}}{36}u^{\left( 4 \right) }
		 -\frac{k^{4}}{48}\left( u'' \right)^{3}+\frac{k^{4}}{144}u'''u''+\mathrm{O}\left( k^{5} \right)  \right]\\
		=&\mathrm{O}\left( k^{5} \right). 
	\end{split}
\end{equation*}
The second equation is achieved by replacing $u\left( t_{n+1} \right) $ with its taylor expansion on $t_n$ and each  $\tilde{y}_i$ with the results above.
Thus we have proved Lemma 7.183.

\section*{Exercise 7.189}
By Exercise 7.259 and $u'\left( t \right)=\lambda u $, we have
\begin{equation*}
	\begin{split}
		ky_1 &= kf\left( U^{n},t_n \right) = k\lambda U^{n} = zU^{n}\\
		ky_2 &= kf\left( U^{n} + \frac{k}{4}y_1 + \frac{k}{4}y_2,t_n+\frac{k}{2} \right)
		     =k\lambda\left( U^{n} + \frac{ky_1}{4} + \frac{ky_2}{4} \right)
		     \Rightarrow ky_2 = \frac{4z + z^2}{4-z}U^{n}\\
		ky_3 &=kf\left( U^{n} + \frac{k}{3}y_1 + \frac{k}{3}y_2 + \frac{k}{3}y_3,t_n +k \right)
		     =k\lambda\left( U^{n} + \frac{ky_1}{3}+\frac{ky_2}{3}+\frac{ky_3}{3} \right)
		\Rightarrow ky_3=\frac{12z + 5z^2}{\left( 3-z \right)\left( 4-z \right)  }U^{n}\\
		U^{n+1}&=U^{n} + \frac{ky_1}{3} + \frac{ky_2}{3}+\frac{ky_3}{3}\\
		       &=\left(1+\frac{z}{3}+\frac{4z+z^2}{3\left( 4-z \right) }
			       +\frac{12z+5z^2}{3\left(3-z  \right)\left( 4-z \right)  }\right)U^{n}\\
		       &=\frac{12+5z}{12-7z+z^2}U^{n}.\\
	\end{split}
\end{equation*}
Thus we have deduced $\mathnormal{R}\left( z \right) $, which is
\[
	\mathnormal{R}\left( z \right)=\frac{1+\frac{5}{12}z}{1-\frac{7}{12}z+\frac{1}{12}z^2} 
.\] 

For $\mathnormal{R}\left( z \right)-e^{z} $, we have
\begin{equation*}
	\begin{split}
		\mathnormal{R}\left( z \right)-e^{z}
		&=\frac{12+5z}{12-7z+z^2}-1-z-\frac{1}{2}z^2+\mathrm{O}\left( z^{3} \right)\quad z\to 0\\  
		&=\frac{24+10z-(24-14z+2z^2)-(24-14z+2z^{2})z-(12-7z+z^{2})z^2}{24-14z+2z^2}+\mathrm{O}\left( z^{3} \right)\quad z\to 0\\
		&=\frac{5z^{3}-z^{4}}{24-14z+2z^{2}}+\mathrm{O}\left( z^{3} \right)\quad z\to 0\\
		&=\mathrm{O}\left( z^{3} \right)+\mathrm{O}\left( z^{3} \right)\quad z\to 0\\
		&=\mathrm{O}\left( z^{3} \right) \quad z\to 0. 
	\end{split}
\end{equation*}

\section*{Exercise 7.205}
I wrote a c++ program to reproduce the results in Example 7.204, the results is stored in two txt files. As 3 cannot be divided by 0.4, I chose 0.5 as the first step length.

\begin{equation*}
	\begin{tabular}{c| c c c}
		&k&BackwardEuler&Trapezoidal\\
		\hline
		&0.2&9.773074e-08&4.722891e-10\\
		$\eta=1$&0.1&4.922329e-08& 1.177188e-10\\
		&0.05&2.468586e-08&2.940792e-11\\
		\hline
		&0.2&9.773074e-08&4.998500e-01\\
		$\eta=1.5$&0.1&4.922329e-08& 4.994004e-01\\
		&0.05&2.468586e-08& 4.976058e-01\\
	\end{tabular}
\end{equation*}

The figure \ref{figure2} shows the picture of the exact solution the IVP (7.131) with initial value $u\left( 0 \right)=1.5 $. 
From the figure we can see a sharp decrease from 1.5 to 1 before t=0.1.
This is caused by the small coefficient $e^{\lambda t}$. 
As $\lambda$ is small enough, the first term of the exact solution in Example 7.192 will decrease steeply 
and the second term $\cos t$ will take the dominant place.

For $\eta = 1$, the exact solution is $\cos t$, so we will not see the sharp decrease. Obviously, each method works properly.

While for $\eta = 1.5$, when we solve the IVP with Backward Euler method, we will step to the $\cos t$-dominanting part in the first step, 
and we get the information of the ODE totally from $U^{n+1}$, which lies on $\cos t$.
Obviously the solution will easily converge to the exact solution near $\cos\left( 3 \right) $.
This meets the L-stable property of Backward Euler method that $U^{n}$ takes less effect on calculating $U^{n+1}$ than the ODE itself.
But when we solve the IVP with Trapezoidal method, in the frist step, we get the information of the ODE partly from the initial point, 
at which the solution is near 1.5 and is far from $\cos t$.
As a result, the solution of $U^{n+1}$ is not close to $\cos t$, which induces error to the solution on T. For Trapezoidal method, not only the ODE itself but also the last step $U^{n}$ will take place in calculating the next step $U^{n+1}$.
So in this IVP, the steep decrease causes bad error pattern.

\begin{figure}[h]
	\centering
                \includegraphics[width=10cm, height=10cm]{IVP_plot.eps}
		\caption{The figure of the exact solution of IVP(7.131) with $u\left( 0 \right)=1.5 $}
		\label{figure2}
\end{figure}
\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
